#+TITLE: The Seasoned Schemer Notes
#+SUBTITLE: Chapter 11
#+AUTHOR: Zelphir Kaltstahl
#+DATE: <2021-08-31>
#+LANGUAGE: English
#+TAGS: Scheme, The Seasoned Schemer
#+CREATOR: Emacs
#+EXCLUDE_TAGS: noexport, notexported
#+OPTIONS: ^:{} H:10 toc:2
#+STARTUP: content indent align inlineimages hideblocks entitiesplain nologdone nologreschedule nologredeadline nologrefile

* Prerequisites

#+NAME: defatom
#+BEGIN_SRC scheme :noweb yes :results none :exports none :eval never-export
(define atom?
  (λ (x)
    (and (not (pair? x))
         (not (null? x)))))
#+end_src

#+NAME: defonep
#+BEGIN_SRC scheme :noweb yes :results none :exports none :eval never-export
(define one?
  (λ (x)
    ;; In theory we could define other things as numbers, for example church
    ;; numerals.
    (= x 1)))
#+end_src

#+NAME: defpick
#+BEGIN_SRC scheme :noweb yes :results none :exports none :eval never-export
(define pick
  (λ (n lat)
    (cond
     [(one? n) (car lat)]
     [else
      (pick (- n 1) (cdr lat))])))
#+end_src

#+NAME: prereq
#+BEGIN_SRC scheme :noweb yes :results none :exports code :eval never-export
<<defatom>>

<<defonep>>

<<defpick>>
#+END_SRC

* Chapter 11

** member?

#+NAME: recapmember
#+begin_src scheme :noweb yes :results none :exports code :eval never-export :language guile
(define member?
  (λ (a lat)
    (cond
     [(null? lat) #f]
     [else
      (or (eq? a (car lat))
          (member? a (cdr lat)))])))
#+end_src

Lets test it:

#+NAME: tryrecapmember
#+begin_src scheme :noweb yes :results output :exports both :eval never-export
<<recapmember>>

(display
 (simple-format
  #f "(member? 1 '(3 2 1)) -> ~a\n"
  (member? 1 '(3 2 1))))

(display
 (simple-format
  #f "(member? 1 '(3 2 4)) -> ~a\n"
  (member? 1 '(3 2 4))))
#+end_src

#+RESULTS: tryrecapmember
: (member? 1 '(3 2 1)) -> #t
: (member? 1 '(3 2 4)) -> #f

** two-in-a-row?

A function shall be defined, which determines, whether there are 2 subsequent elements inside a given list, for which ~eq?~ is ~#t~.

#+NAME: is-first-a
#+begin_src scheme :noweb yes :results none :exports none :eval never-export
(define is-first?
  (λ (a lat)
    (cond
     [(null? lat) #f]
     [else (eq? a (car lat))])))
#+end_src

#+NAME: two-in-a-row-v1
#+begin_src scheme :noweb yes :results none :exports code :eval never-export
<<is-first-a>>

(define two-in-a-row?
  (λ (lat)
    (cond
     [(null? lat) #f]
     [else
      (or (is-first? (car lat) (cdr lat))
          (two-in-a-row? (cdr lat)))])))
#+end_src

#+RESULTS: two-in-a-row-v1

However, this version obscures, that in one case it performs a check twice. When it checks, whether the list is ~null?~ in ~is-first?~ and returns ~#f~, ~two-in-a-row?~ will recur and call itself. Then it will check for a second time, whether the list it receives is ~null?~. To avoid this duplicate check, the book suggests to leave the decision of whether to recur or not to the function, which checks for en empty list first. That is ~is-first?~.

Let us try to leave that responsibility to ~is-first?~:

#+NAME: is-first-b
#+begin_src scheme :noweb yes :results none :exports none :eval never-export
(define is-first-b?
  (λ (a lat)
    (cond
     [(null? lat) #f]
     [else
      (or (eq? a (car lat))
          ;; Not (cdr lat) here! is-first-b? is already given the cdr of the
          ;; list and the argument ~a~ is the actual car of the list!
          (two-in-a-row? lat))])))
#+end_src

#+NAME: two-in-a-row-v2
#+begin_src scheme :noweb yes :results none :exports code :eval never-export
<<is-first-b>>

(define two-in-a-row?
  (λ (lat)
    (cond
     [(null? lat) #f]
     [else
      (is-first? (car lat) (cdr lat))])))
#+end_src

Now we have two functions which are mutually recursive.

(Note: There is also a problem of src_scheme[:exports code]{(two-in-a-row? lat)} in ~is-first-b?~ not being in the tail position and thus growing the stack each call.)

There is still a duplicate check of src_scheme[:exports code]{(null? lat)}, because when ~two-in-a-row?~ is called from ~is-first-b?~, it checks again, whether the list is empty.

When we look at what ~two-in-a-row?~ actually does, when called from ~is-first-b?~, we can see, that it does not actually do much. The ~null?~ check for the empty list will always be ~#f~, because the same thing was already checked in ~is-first-b?~ about ~lat~ and ~lat~ is given to ~two-in-a-row?~. So ~two-in-a-row?~ will always enter the ~else~ branch, when called from ~is-first-b?~ and the ~null?~ check is only useful, when ~two-in-a-row?~ is initially called from outside of ~is-first-b?~. This observation leads to the conclusion, that one could write a single function, by modifying ~is-first-b?~ a little more, so that the call to ~two-in-a-row?~ is no longer needed.

The modified version of ~is-first-b?~ will be renamed to ~two-in-a-row-b?~ to express what it does.

#+NAME: two-in-a-row-b
#+begin_src scheme :noweb yes :results none :exports code :eval never-export
(define two-in-a-row-b?
  (λ (preceding lat)
    (cond
     [(null? lat) #f]
     [else
      (or (eq? preceding (car lat))
          (two-in-a-row-b? (car lat) (cdr lat)))])))
#+end_src

There is still a problem here: ~two-in-a-row-b?~ receives always 2 arguments. This is inconvenient and unexpected to work with. One could use ~two-in-a-row?~ to avoid this:

(Note: The problem of non-tail position of the call to ~(two-in-a-row-b? (car lat) (cdr lat))~ still persists.)

#+NAME: two-in-a-row-final
#+begin_src scheme :noweb yes :results none :exports code :eval never-export
<<two-in-a-row-b>>

(define two-in-a-row?
  (λ (lat)
    (cond
     [(null? lat) #f]
     [else
      (two-in-a-row-b? (car lat) (cdr lat))])))
#+end_src

This clears up the interface for the user.

A tail call optimized version, getting rid of the non-tail position of the recursive call, could be written as follows:

#+NAME: two-in-a-row-improved
#+begin_src scheme :noweb yes :results none :exports code :eval never-export
(define two-in-a-row?
  (λ (preceding lat)
    (cond
     [(null? lat) #f]
     ;; It is a bit meh, that we cannot simply return the result of the
     ;; expression here and need to write #t instead. Perhaps there is a better
     ;; way?
     [(eq? preceding (car lat)) #t]
     [else
      ;; Tail-recursive.
      (two-in-a-row-b? (car lat) (cdr lat))])))
#+end_src

** sum-of-prefixes

This part introduces a function, which calculates the sum of the prefix for each element in the given list.

My first attempt:

#+NAME: my-sum-of-prefixes
#+begin_src scheme :noweb yes :results none :exports code :eval never-export
(define sum-of-prefixes
  (λ (tup)

    (define iter
      (λ (tup prefix-sum)
        (cond
         [(null? tup)
          (cons prefix-sum '())]
         [else
          (cons prefix-sum
                (iter  (cdr tup)
                       (+ prefix-sum (car tup))))])))

    (cond
     [(null? tup) '()]
     [else
      (iter (cdr tup) (car tup))])))
#+end_src

Let us try it:

#+NAME: try-my-sum-of-prefixes
#+begin_src scheme :noweb yes :results output :exports both :eval never-export
<<my-sum-of-prefixes>>

(display
 (simple-format
  #f "(sum-of-prefixes '(1 1 1 1 1)) -> ~a\n"
  (sum-of-prefixes '(1 1 1 1 1))))
#+end_src

#+RESULTS: try-my-sum-of-prefixes
: (sum-of-prefixes '(1 1 1 1 1)) -> (1 2 3 4 5)

The book does not make use of inner definitions using ~define~. Instead it uses additional functions defined separately:

#+NAME: sum-of-prefixes
#+begin_src scheme :noweb yes :results none :exports code :eval never-export
(define sum-of-prefixes
  (λ (tup)
    ;; Start with a sum of 0, the neutral element of addition.
    (sum-of-prefixes-b 0 tup)))


(define sum-of-prefixes-b
  (λ (sonssf tup)
    (cond
     [(null? tup) '()]
     [else
      (cons (+ sonssf (car tup))
            (sum-of-prefixes-b (+ sonssf (car tup))
                               (cdr tup)))])))
#+end_src

Let us try it:

#+NAME: try-sum-of-prefixes
#+begin_src scheme :noweb yes :results output :exports both :eval never-export
<<sum-of-prefixes>>

(display
 (simple-format
  #f "(sum-of-prefixes '(1 1 1 1 1)) -> ~a\n"
  (sum-of-prefixes '(1 1 1 1 1))))
#+end_src

#+RESULTS: try-sum-of-prefixes
: (sum-of-prefixes '(1 1 1 1 1)) -> (1 2 3 4 5)

~sum-of-prefixes~ just like in my own solution takes only one argument, so that the caller does not need to think about the implementation detail. The interface is simple. The definition in the book has advantages and disadvantages. An advantage is, that the code is less nested. A disadvantage is, that ~sum-of-prefixes-b~ pollutes the namespace of the module, in which it is defined and serves no other purpose than being called by ~sum-of-prefixes~.

The point the book makes is, that for recursive functions, which need to know about previous arguments to the function, one can define a helper function, which takes additional arguments. This is stated in the Eleventh Commandment:

#+begin_quote
Use additional arguments when a function needs to know what other arguments to the function have been like so far.
#+end_quote

** scramble

Next the book goes on to show a weird but in principle similar example ~scramble~, which takes a tuple and calculates another tuple from it:

#+NAME: scramble
#+begin_src scheme :noweb yes :results none :exports code :eval never-export
<<defonep>>


<<defpick>>


(define scramble
  (λ (tup)
    (scramble-b tup '())))


(define scramble-b
  (λ (tup rev-pre)
    (cond
     [(null? tup) '()]
     [else
      (cons
       (pick (car tup)
             ;; Here we artificially make the reversed prefix longer by the
             ;; current element, so that pick will pick the correct element.
             (cons (car tup) rev-pre))
       (scramble-b (cdr tup)
                   ;; We add the current element to the reversed prefix of the
                   ;; next iteration.
                   (cons (car tup) rev-pre)))])))
#+end_src

The ~scramble~ function looks at each number in the tuple. The number at each position (position = index + 1, or "distance from the start of the list") is substracted from its position and the resulting value is the index of the value, which shall be the final result for the number in the resulting tuple.

Let us try it:

#+NAME: try-scramble
#+begin_src scheme :noweb yes :results output :exports both :eval never-export
<<scramble>>

(display
 (simple-format
  #f "(scramble '(1 2 3 1 2 3 4 1 8 2 10)) -> ~a\n"
  (scramble '(1 2 3 1 2 3 4 1 8 2 10))))
#+end_src

#+RESULTS: try-scramble
: (scramble '(1 2 3 1 2 3 4 1 8 2 10)) -> (1 1 1 1 1 1 1 1 2 8 2)
